package a3_p04_ak_fh;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.jgrapht.WeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.WeightedMultigraph;
import org.jgrapht.util.FibonacciHeap;
import org.jgrapht.util.FibonacciHeapNode;
import a3_p04_ak_fh.FibHeapElement;

import a2_p04_ak_fh.AttVertex;

public class Prim {

	private WeightedGraph<AttVertex, DefaultWeightedEdge> mingraph = new WeightedMultigraph<AttVertex, DefaultWeightedEdge>(
			DefaultWeightedEdge.class);
	private long time = 0;
	private int hits = 0;
	private double weightsum = 0.0;
	private Map<AttVertex, DefaultWeightedEdge> queue = new HashMap<AttVertex, DefaultWeightedEdge>();
	private Map<AttVertex, FibonacciHeapNode<FibHeapElement>> fibmap = new HashMap<AttVertex, FibonacciHeapNode<FibHeapElement>>();
	private Map<AttVertex, Double> queueFib = new HashMap<AttVertex, Double>();
	private Set<AttVertex> inMinGraph = new HashSet<AttVertex>();
	private FibonacciHeap<FibHeapElement> fibheap = new FibonacciHeap<FibHeapElement>();

	private Prim(WeightedGraph<AttVertex, DefaultWeightedEdge> graph,
			boolean fib) {
		CalcGraph(graph, fib);
	}

	public WeightedGraph<AttVertex, DefaultWeightedEdge> getGraph() {
		return this.mingraph;
	}

	public long getTimeInMillis() {
		return this.time;
	}

	public long getTimeInSec() {
		return this.time / 100;
	}

	public int getHits() {
		return this.hits;
	}

	public double getWeightSum() {
		return this.weightsum;
	}

	public static Prim CalcPriQu(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph) {
		return new Prim(graph, false);
	}

	public static Prim CalcFibHeap(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph) {
		return new Prim(graph, true);
	}

	/**
	 * 
	 * @param graph
	 * @param queue
	 * @return Vertex with minimum distance.
	 */
	private AttVertex getMinVertex(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph,
			Map<AttVertex, DefaultWeightedEdge> queue) {
		double minWeight = Double.MAX_VALUE;
		double nextWeight = 0;
		AttVertex minVertex = null;
		for (Map.Entry<AttVertex, DefaultWeightedEdge> queueElement : queue
				.entrySet()) {
			nextWeight = graph.getEdgeWeight(queueElement.getValue());
			if (nextWeight < minWeight) {
				minWeight = nextWeight;
				minVertex = queueElement.getKey();
			}
		}
		return minVertex;
	}
	
	/**
	 * This method checks if the vertex should added to the queue
	 * @param graph
	 * @param vertex ; source or target
	 * @param edge
	 */
	private void checkHeapUpdate(WeightedGraph<AttVertex, DefaultWeightedEdge> graph,
			AttVertex vertex,DefaultWeightedEdge edge){
		if (!inMinGraph.contains(vertex))
			if (!queue.containsKey(vertex)) {
				queue.put(vertex, edge);
			} else if (graph.getEdgeWeight(queue.get(vertex)) > graph
					.getEdgeWeight(edge)) {
				queue.put(vertex, edge);
			}
	}
	
	/**
	 * This method update the heap by adding the new targets from the given vertex
	 * @param graph
	 * @param vertex
	 */
	private void updatePutHeap(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph,
			AttVertex vertex) {
		for (DefaultWeightedEdge edge : graph.edgesOf(vertex)) {
			AttVertex source = graph.getEdgeSource(edge);
			AttVertex target = graph.getEdgeTarget(edge);
			if (vertex.equals(source)) {
				checkHeapUpdate(graph,target,edge);
			} else {
				checkHeapUpdate(graph,source,edge);
			}
		}
	}
	
	/**
	 * This method checks if the vertex should added to the fibheap
	 * @param graph
	 * @param vertex ; source or target
	 * @param edge
	 */
	private void checkFibUpdate(WeightedGraph<AttVertex, DefaultWeightedEdge> graph,
			AttVertex vertex,DefaultWeightedEdge edge){
		if (!inMinGraph.contains(vertex)) {
			if (queueFib.containsKey(vertex)) {
				//Check if this edge is better
				if (graph.getEdgeWeight(edge) < queueFib.get(vertex)) {
					fibheap.decreaseKey(fibmap.get(vertex),
							graph.getEdgeWeight(edge));
					queueFib.put(vertex, graph.getEdgeWeight(edge));
				}
			} else {
				FibonacciHeapNode<FibHeapElement> node = new FibonacciHeapNode<FibHeapElement>(
						new FibHeapElement(vertex, edge));
				fibheap.insert(node, graph.getEdgeWeight(edge));
				//Map for getting the fibHeapNode. -> DecreaseKey
				fibmap.put(vertex, node);
				//Queue for getting the EdgeWeight of a inserted vertex
				queueFib.put(vertex, graph.getEdgeWeight(edge));
			}
		}
	}
	
	/**
	 * This method update the fibheap by adding the new targets from the given vertex
	 * @param graph
	 * @param vertex
	 */
	private void updatePutFibHeap(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph,
			AttVertex vertex) {
		for (DefaultWeightedEdge edge : graph.edgesOf(vertex)) {
			AttVertex source = graph.getEdgeSource(edge);
			AttVertex target = graph.getEdgeTarget(edge);
			if (vertex.equals(source)) {
				checkFibUpdate(graph,target,edge);
			} else {
				checkFibUpdate(graph,source,edge);
			}

		}
	}

	private void CalcGraph(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph, boolean fib) {

		Set<AttVertex> allVertices = new HashSet<AttVertex>();

		allVertices = graph.vertexSet();
		AttVertex vertex = (AttVertex) (allVertices.toArray())[0];
		AttVertex nextVertex = null;
		mingraph.addVertex(vertex);

		this.inMinGraph.add(vertex);
		this.hits++;
		this.time = System.currentTimeMillis();
		if (!fib) {
			updatePutHeap(graph, vertex);
			while (!this.queue.isEmpty()) {
				nextVertex = getMinVertex(graph, this.queue);
				this.mingraph.addVertex(nextVertex);
				DefaultWeightedEdge minEdge = this.queue.get(nextVertex);
				this.mingraph.addEdge(graph.getEdgeSource(minEdge),
						graph.getEdgeTarget(minEdge), minEdge);
				this.weightsum += this.mingraph.getEdgeWeight(minEdge);
				this.inMinGraph.add(nextVertex);
				this.queue.remove(nextVertex);
				vertex = nextVertex;
				updatePutHeap(graph, nextVertex);
				this.hits++;
			}
		} else {
			updatePutFibHeap(graph, vertex);
			while (!this.fibheap.isEmpty()) {
				FibonacciHeapNode<FibHeapElement> nextVertexNode = this.fibheap
						.removeMin();
				nextVertex = nextVertexNode.getData().getVertex();
				this.mingraph.addVertex(nextVertex);
				this.mingraph
						.addEdge(graph.getEdgeSource(nextVertexNode.getData()
								.getEdge()), graph.getEdgeTarget(nextVertexNode
								.getData().getEdge()), nextVertexNode.getData()
								.getEdge());

				this.weightsum += nextVertexNode.getKey();

				this.inMinGraph.add(nextVertex);
				vertex = nextVertex;
				updatePutFibHeap(graph, nextVertex);
				this.hits++;
			}
		}

		this.time = System.currentTimeMillis()-this.time;
		System.out.println("Kantengewichtssumme: " + weightsum);
		System.out.println("Zugriffe: " + hits);
		System.out.println("Zeit[sec]: " + this.getTimeInSec());
		System.out.println("Zeit[msec]: " + this.getTimeInMillis());
	}

}
